﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sort
{
    class MergeSort
    {
        static void Main()
        {
            Console.WriteLine("MergeSort.");
            int[] arr = { 10, 1, 2, 3, 5, 0, 9, 8, 7, 6, 4 };
            Random rd = new Random();
            for (int j = 0; j < 1000; j++)
            {
                for (int i = 0; i < 10; i++)
                {
                    arr[i] = rd.Next(20);
                }
                Sort(arr);
                if (!Utils.CheckOrderArray(arr))
                {
                    Console.WriteLine("error.");
                }
                //Utils.WriteArr(arr);
            }
        }

        public static void Sort(int[] arr)
        {
            int gap = 1;
            int beg = 0;
            int size = arr.Length;

            while (gap < size)
            {
                while (beg + gap < size)
                {
                    Merge(arr, beg, beg + gap, beg + 2 * gap - 1);
                    beg += (2 * gap);
                }
                gap *= 2;
                beg = 0;
            }
        }

        static void Merge(int[] arr, int beg, int mid, int end)
        {
            
            if (mid >= arr.Length)
            {
                return;
            }

            if (end >= arr.Length)
            {
                end = arr.Length - 1;
            }

            int i = beg;
            int j = mid;
            int k = 0;
            int size = end - beg + 1;
            int[] arrTemp = new int[size];

            while (i < mid && j <= end)
            {
                if (arr[i] <= arr[j])
                {
                    arrTemp[k++] = arr[i++];
                }
                else
                {
                    arrTemp[k++] = arr[j++];
                }
            }

            if (i < mid)
            {
                for (int n = i; n < mid; n++)
                {
                    arrTemp[k++] = arr[n];
                }
            }

            if (j <= end)
            {
                for (int n = j; n <= end; n++)
                {
                    arrTemp[k++] = arr[n];
                }
            }

            for (int n = 0; n < size; n++)
            {
                arr[beg + n] = arrTemp[n];
            }
        }
    }
}
